package edu.whu.rose.clock.ssql.index;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Date;
import java.util.HashMap;

public class EdgeMatrix {

	private final int order;
	
	private HashMap<Integer,EdgeNode> rowHeads;
	private HashMap<Integer,EdgeNode> columnHeads;
	
	private int power;
	
	public EdgeMatrix(int order) {
		this.order = order;
		this.rowHeads = new HashMap<Integer,EdgeNode>();
		this.columnHeads = new HashMap<Integer,EdgeNode>();
	}
	
	public static void main(String[] args) {
		EdgeMatrix rm = new EdgeMatrix(1754297);
		rm.fillDiagonalNodes();
		rm.load("graph/edge.txt");
		rm = rm.multiply(rm);
		
//		EdgeMatrix rm = new EdgeMatrix(4);
//		rm.fillDiagonalNodes();
//		EdgeMatrix orm = new EdgeMatrix(4);
//		orm.fillDiagonalNodes();
//		rm.load();
//		orm.load();
//		rm = rm.multiply(orm);
//		rm = rm.multiply(orm);
		
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			while (true) {
				System.out.println("Please input query:");
				String statement = br.readLine().trim();
				if (!statement.equals("exit")) {
					String[] nums = statement.split(",");
					System.out.println(rm.get(new Integer(nums[0].trim()).intValue(), new Integer(nums[1].trim()).intValue()));
				}
				else {
					break;
				}
			}
			br.close();
		}
		catch (IOException ex) {
			ex.printStackTrace();
		}
	}
	
	public void load() {
		this.insert(0, 1);
		this.insert(1, 3);
		this.insert(0, 2);
		this.insert(2, 1);
		this.insert(3, 2);
//		this.insert(1, 2);
//		this.insert(2, 1);
	}
	
	public void load(String dataFile) {
		try {
			BufferedReader br = new BufferedReader(new FileReader(dataFile));
			while (br.ready()) {
				String line = br.readLine().trim();
				String edge = line.substring(line.lastIndexOf(" ") + 1);
				int pos1 = edge.indexOf("-->");
				int pos2 = edge.indexOf(":");
				if (pos1 == -1 || pos2 == -1) {
					System.err.println("Found a wrong edge: " + edge);
					continue;
				}
				int row = new Integer(edge.substring(0, pos1)).intValue() - 1;
				int column = new Integer(edge.substring(pos1 + 3, pos2)).intValue() - 1;
				this.insert(row, column);
			}
			System.out.println("Loading finished");
			br.close();
		}
		catch (IOException ex) {
			ex.printStackTrace();
		}
	}
	
//	public void power() {
//		if (power > 0 ) {
//			this.power(power);
//		}
//	}
//	
//	public void power(int r) {
//		power = r;
//		
//		String[][] temp1 = new String[order][order];
//		this.copy(matrix, temp1);
//		String[][] temp2 = null;
//		for (int i = 0; i < r - 1; i++) {
//			temp2 = this.multiply(temp1, matrix);
//			temp1 = temp2;
//		}
//		matrix_r = temp1;
//	}
	
//	private void selfCopy() {
//		
//	}
	
	public EdgeMatrix multiply(EdgeMatrix multiplicand) {
		EdgeMatrix result = new EdgeMatrix(order);
		Date start = new Date();
		Date end = null;
		for (int i = 0; i < order; i++) {
			if (i % 100 == 0) {
				end = new Date();
				System.out.println(i + " : " + (end.getTime() - start.getTime()));
			}
			Integer r = new Integer(i);
			if (this.rowHeads.get(r) == null) {
				continue;
			}
			EdgeNode rowIndex = null;
			//------------------------important------------------------------
			for (int j = 0; j < order; j++) {
			//------------------------important------------------------------
				boolean newEdge = false;
				rowIndex = this.rowHeads.get(r);
				Integer c = new Integer(j);
				EdgeNode columnIndex = multiplicand.columnHeads.get(c);
				while (rowIndex != null && columnIndex != null) {
					if (rowIndex.getColumn() < columnIndex.getRow()) {
						rowIndex = rowIndex.getNextNodeInSameRow();
					}
					else if (rowIndex.getColumn() > columnIndex.getRow()) {
						columnIndex = columnIndex.getNextNodeInSameColumn();
					}
					else {
						if (rowIndex.getEdge() && columnIndex.getEdge()) {
							result.insert(i, j);
							break;
						}
						rowIndex = rowIndex.getNextNodeInSameRow();
						columnIndex = columnIndex.getNextNodeInSameColumn();
					}
				}
			}
		}
		return result;
	}
	
	public void insert(int row, int column) {
		if (row > order - 1 | column > order - 1 | row < 0 | column < 0) {
			System.out.println("Error: position (" + row + "," + column + ")");
			return;
		}
		EdgeNode newNode = new EdgeNode(row, column, true);
		Integer r = new Integer(row);
		Integer c = new Integer(column);
		EdgeNode rowHead = this.rowHeads.get(r);
		EdgeNode columnHead = this.columnHeads.get(c);
		if (rowHead == null) {
			this.rowHeads.put(r, newNode);
		}
		else {
			if (rowHead.getColumn() > column) {
				newNode.setNextNodeInSameRow(rowHead);
				this.rowHeads.put(r, newNode);
			}
			else if (rowHead.getColumn() < column) {
				EdgeNode rd = null;
				for (rd = rowHead; rd.getNextNodeInSameRow() != null && 
				rd.getNextNodeInSameRow().getColumn() < column; rd = rd.getNextNodeInSameRow());
				if (rd.getNextNodeInSameRow() == null) {
					rd.setNextNodeInSameRow(newNode);
				}
				else {
					newNode.setNextNodeInSameRow(rd.getNextNodeInSameRow());
					rd.setNextNodeInSameRow(newNode);
				}
			}
		}
		if (columnHead == null) {
			this.columnHeads.put(c, newNode);
		}
		else {
			if (columnHead.getRow() > row) {
				newNode.setNextNodeInSameColumn(columnHead);
				this.columnHeads.put(c, newNode);
			}
			else if (columnHead.getRow() < row) {
				EdgeNode rd = null;
				for (rd = columnHead; rd.getNextNodeInSameColumn() != null && 
				rd.getNextNodeInSameColumn().getRow() < row; rd = rd.getNextNodeInSameColumn());
				if (rd.getNextNodeInSameColumn() == null) {
					rd.setNextNodeInSameColumn(newNode);
				}
				else {
					newNode.setNextNodeInSameColumn(rd.getNextNodeInSameColumn());
					rd.setNextNodeInSameColumn(newNode);
				}
			}
		}
	}
	
	public boolean get(int row, int column) {
		if (row < column) {
			Integer c = new Integer(column);
			EdgeNode columnHead = this.columnHeads.get(c);
			if (columnHead == null) {
				return false;
			}
			if (columnHead.getRow() == row) {
				return columnHead.getEdge();
			}
			else if (columnHead.getRow() > row) {
				return false;
			}
			else {
				EdgeNode rd = null;
				for (rd = columnHead; rd.getNextNodeInSameColumn() != null && 
				rd.getNextNodeInSameColumn().getRow() < row; rd = rd.getNextNodeInSameColumn());
				if (rd.getNextNodeInSameColumn() == null || rd.getNextNodeInSameColumn().getRow() > row) {
					return false;
				}
				else {
					return rd.getNextNodeInSameColumn().getEdge();
				}
			}
		}
		else {
			Integer r = new Integer(row);
			EdgeNode rowHead = this.rowHeads.get(r);
			if (rowHead == null) {
				return false;
			}
			if (rowHead.getColumn() == column) {
				return rowHead.getEdge();
			}
			else if (rowHead.getRow() > row) {
				return false;
			}
			else {
				EdgeNode rd = null;
				for (rd = rowHead; rd.getNextNodeInSameRow() != null && 
				rd.getNextNodeInSameRow().getColumn() < column; rd = rd.getNextNodeInSameRow());
				if (rd.getNextNodeInSameRow() == null || rd.getNextNodeInSameRow().getColumn() > column) {
					return false;
				}
				else {
					return rd.getNextNodeInSameRow().getEdge();
				}
			}
		}
	}
	
	public void fillDiagonalNodes() {
		for (int i = 0; i < order; i++) {
			this.insert(i, i);
		}
	}

	public HashMap<Integer, EdgeNode> getRowHeads() {
		return rowHeads;
	}

	public HashMap<Integer, EdgeNode> getColumnHeads() {
		return columnHeads;
	}

}
